home *** CD-ROM | disk | FTP | other *** search
/ BMUG PD-ROM A / PD-ROM A.iso / Programming / Programming Help / Alpha.4.01 / ACMDS / acmds.new / sort.c < prev   
Encoding:
C/C++ Source or Header  |  1991-07-29  |  4.5 KB  |  297 lines  |  [TEXT/ALFA]
  1. /* Sort ACMD */
  2.  
  3. #include    "MacHeaders"
  4. #include     "stdlib.h"
  5. #include    "SetUpA4.h"
  6.  
  7. #define    TRUE    1
  8. #define    FALSE    0
  9. #define    CR        '\r'
  10.  
  11. #undef    DEBUG
  12.  
  13.  
  14. /* pointer to a function that returns an 'int' */
  15. typedef int      (*FPtr)();
  16.  
  17. /* global variables */
  18. long            sortCol = 0;
  19. static char     *qBase;
  20. static size_t     qSize;
  21. static int         (*qCompare)();
  22. static int         (*q1Compare)();
  23. static void     (*q1Swap)();
  24.  
  25. static int         std_compare(size_t, size_t);
  26. static void     std_swap(size_t, size_t);
  27.  
  28. static void     qsort1(size_t, size_t);
  29. static void     aqsort(void *, size_t, size_t, int (*)());
  30.  
  31. FPtr    theAlert;
  32.  
  33. char *
  34. #ifdef    DEBUG
  35. sort(text, alert, getVar, setVar, defineVar,deleteVar)
  36. #else
  37. main(text, alert, getVar, setVar, defineVar,deleteVar)
  38. #endif    DEBUG
  39. char    *text;
  40. FPtr    getVar, setVar, defineVar, deleteVar, alert;
  41. {
  42.     long            lines,i;
  43.     register char    *ptr, *ptr2;
  44.     char            **ptrs, *toPtr;
  45.     int                endingCr = FALSE;
  46.     int                lineCompare();
  47.  
  48. #ifndef    DEBUG
  49.     /* this self-modifying stuff will crash under A/UX... */
  50.     RememberA0();
  51.     SetUpA4();
  52.  
  53.     if (!getVar("sortColumn", &sortCol))
  54.     {
  55.         alert("Unable to access vars");
  56.         DisposPtr(text);
  57.         return NULL;
  58.     }
  59. #endif    DEBUG
  60.     theAlert = alert;    
  61.  
  62.     for (ptr = text, lines = 1; *ptr; ptr++) if (*ptr == CR) lines++;
  63.     if (*(ptr - 1) == CR)
  64.     {
  65.         endingCr = TRUE;
  66.         lines--;
  67.     }
  68.     
  69.     if (!(ptrs = NewPtr(sizeof(char *) * (lines + 1)))) /* extra for an ending cr we don't use */
  70.     {
  71.         alert("sort: unable to allocate, error %d", MemError());
  72. #ifndef    DEBUG
  73.         RestoreA4();
  74. #endif    DEBUG
  75.         return text;
  76.     }
  77.     
  78.     ptrs[0] = text;
  79.     for (ptr = text, i = 1; *ptr; ptr++)
  80.     {
  81.         if (*ptr == CR) ptrs[i++] = ptr + 1;
  82.     }
  83.     *ptr = CR;
  84.     
  85.     aqsort(ptrs, (long)lines, (long)sizeof(char *), lineCompare);
  86.     
  87.     if (!(toPtr = NewPtr(GetPtrSize(text) + 1)))
  88.     {
  89.         alert("sort: unable to allocate, error %d", MemError());
  90. #ifndef    DEBUG
  91.         RestoreA4();
  92. #endif    DEBUG
  93.         return text;
  94.     }
  95.     
  96.     for (i = 0, ptr2 = toPtr; i < lines; i++)
  97.     {
  98.         for (ptr = ptrs[i]; *ptr != CR;)
  99.         {
  100.             *ptr2++ = *ptr++;
  101.         }
  102.         *ptr2++ = CR;
  103.     }
  104.     if (endingCr) 
  105.         *ptr2++ = 0;
  106.     else
  107.         *(ptr2 - 1) = 0;
  108.     
  109.     /* paranoia */
  110.     if ((ptr2 - toPtr) > GetPtrSize(toPtr))
  111.     {
  112.         alert("sort: overran bounds!");
  113.     }
  114.     
  115.     /* clean up */
  116.     DisposPtr(text);
  117.  
  118. #ifndef    DEBUG
  119.     RestoreA4();
  120. #endif    DEBUG
  121.  
  122.     return toPtr;
  123. }
  124.  
  125.  
  126. /* return first minus second */
  127. lineCompare(sptr1, sptr2)
  128. char    **sptr1, **sptr2;
  129. {
  130.     register char    *ptr1 = *sptr1, *ptr2 = *sptr2;
  131.     int                i;
  132.  
  133.  
  134.     for (i = 0; i < sortCol; i++)
  135.     {
  136.         if (*ptr1++ == CR)
  137.         {
  138.             return  (*ptr2 == CR) ? 0 : -1;
  139.         }
  140.         if (*ptr2++ == CR)
  141.         {
  142.             return (1);
  143.         }
  144.     }
  145.     
  146.     for (; *ptr1 != CR; ptr1++, ptr2++)
  147.     {
  148.         if (*ptr1 != *ptr2)
  149.         {
  150.             if (*ptr2 == CR)
  151.             {
  152.                 return (1);
  153.             }
  154.             else
  155.             {
  156.                 return (*ptr1 - *ptr2);
  157.             }
  158.         }
  159.     }
  160.     return  ((*ptr2 == CR) ? 0 : -1);
  161. }
  162.  
  163.     
  164.  
  165.  
  166. #ifdef    DEBUG
  167. main()
  168. {
  169.     char    *text = "one\rtwo\rthree\r";
  170.     char    *ptr;
  171.     
  172.     ptr = NewPtr(200);
  173.     memmove(ptr, text, (long)(strlen(text) + 1));
  174.     ptr = sort(ptr);
  175.     printf("Result: '%s'\n",ptr);
  176. }
  177. #endif    DEBUG
  178.  
  179. /*
  180.  *  qsort.c
  181.  *
  182.  *  Copyright (c) 1989 Symantec Corporation.  All rights reserved.
  183.  *
  184.  */
  185.  
  186.  
  187.  
  188. /* ---------- standard quicksort ---------- */
  189.  
  190.  
  191. void
  192. aqsort(base, n, size, compare)
  193. void *base;
  194. size_t n, size;
  195. int (*compare)();
  196. {
  197.     qBase = base;
  198.     qSize = (size + 1) & ~1;
  199.     qCompare = compare;
  200.     _aqsort(n, std_compare, std_swap);
  201. }
  202.  
  203.  
  204. static int
  205. std_compare(i, j)
  206. size_t i, j;
  207. {
  208.     return((*qCompare)(qBase + i * qSize, qBase + j * qSize));
  209. }
  210.  
  211.  
  212. static void
  213. std_swap(i, j)
  214. size_t i, j;
  215. {
  216.     register void *p = qBase + i * qSize;
  217.     register void *q = qBase + j * qSize;
  218.     
  219.     asm {
  220.         move.l    qSize,d0
  221. @1        move.b    (p)+,d1
  222.         eor.b    d1,(q)+
  223.         subq.l    #1,d0
  224.         bne.s    @1
  225.     }
  226.     asm {
  227.         move.l    qSize,d0
  228. @2        move.b    -(q),d1
  229.         eor.b    d1,-(p)
  230.         subq.l    #1,d0
  231.         bne.s    @2
  232.     }
  233.     asm {
  234.         move.l    qSize,d0
  235. @3        move.b    (p)+,d1
  236.         eor.b    d1,(q)+
  237.         subq.l    #1,d0
  238.         bne.s    @3
  239.     }
  240. }
  241.  
  242.  
  243. /* ---------- general quicksort ---------- */
  244.  
  245.  
  246. int
  247. _aqsort(n, compare, swap)
  248. size_t n;
  249. int (*compare)();
  250. void (*swap)();
  251. {
  252.     q1Compare = compare;
  253.     q1Swap = swap;
  254.     qsort1(0, n);
  255. }
  256.  
  257.  
  258. /*
  259.  *  sort elements "first" through "last"-1
  260.  *
  261.  */
  262.  
  263. static void
  264. qsort1(first, last)
  265. size_t first, last;
  266. {
  267.     static size_t i;        /*  "static" to save stack space  */
  268.     size_t j;
  269.  
  270.     while (last - first > 1) {
  271.         i = first;
  272.         j = last;
  273.         for (;;) {
  274.             while (++i < last && (*q1Compare)(i, first) < 0)
  275.                 ;
  276.             while (--j > first && (*q1Compare)(j, first) > 0)
  277.                 ;
  278.             if (i >= j)
  279.                  break;
  280.             (*q1Swap)(i, j);
  281.         }
  282.         if (j == first) {
  283.             ++first;
  284.             continue;
  285.         }
  286.         (*q1Swap)(first, j);
  287.         if (j - first < last - (j + 1)) {
  288.             qsort1(first, j);
  289.             first = j + 1;    /*  qsort1(j + 1, last);  */
  290.         }
  291.         else {
  292.             qsort1(j + 1, last);
  293.             last = j;        /*  qsort1(first, j);  */
  294.         }
  295.     }
  296. }
  297.